/*
    二分查找
    1.朴素二分查找
    2.查找左区间
    3.查找右区间
*/

// class Solution {
// public:
//     int search(vector<int>& nums, int target) {
//         int left = 0, right = nums.size() - 1;
//         while (left <= right) {
//             int mid = left + (right - left) / 2;
//             if (nums[mid] < target)
//                 left = mid + 1;
//             else if (nums[mid] > target)
//                 right = mid - 1;
//             else
//                 return mid;
//         }
//         return -1;
//     }
// };

// class Solution {
// public:
//     int takeAttendance(vector<int>& records) {
//         int left = 0, right = records.size()-1;
//         //二段性: 左段records[i]==i, 右段records[i]==i+1, 找到左段最大值加一
//         while(left < right)
//         {
//             int mid = left + (right - left + 1)/2;
//             if(records[mid] == mid) left = mid;
//             else right = mid - 1;
//         }
//         if(left == 0 && records[left] == 1) return 0;//左段不存在，只有一种情况:0号缺勤
//         return records[left] + 1;
//     }
// };